package q738_monotoneIncreasingDigits;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    /*
    通过贪心的方法来解决此题
    局部最优：
    通过比较转为数组后nums[i] 和 nums[i - 1]的大小
    例如12321111 当到最后一个2时 由于 3 > 2 所以我们将 3 - 1 然后把其后面的所有数都变成9 就能够得到答案

    但是局部最优有一个问题 例如 对于332 当我们比较到2时 只会变为329 这样前面的32又不符合条件
    因此我们需要从后向前遍历 一直到所有数字都满足单调递增 同时利用一个sign记录我们要变化的位置 将sign及其后面的位置全部变成9
     */
    public int monotoneIncreasingDigits(int n) {
        // 先将其转换为list
        List<Integer> nums = new ArrayList<>();
        while (n > 0) {
            nums.add(n % 10);
            n = n / 10;
        }

        int sign = 0, ans = 0;
        // 这里用的是list
        // 通过转换得到的list应该是倒序的 例如 123 ——> 3 2 1
        for (int i = 1; i < nums.size(); i++) {
            if (nums.get(i - 1) < nums.get(i)) {
                sign = i - 1;
                nums.set(i, nums.get(i) - 1);
            }
        }

        for (int size = nums.size() - 1; size >= 0; size--) {
            ans = size <= sign ? ans * 10 + 9 : ans * 10 + nums.get(size);
        }

        return ans;
    }
}
